package com.sheng.leetcode.year2023.month12.day04;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/12/4
 * <p>
 * 1038. 从二叉搜索树到更大和树<p>
 * <p>
 * 给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。<p>
 * 提醒一下， 二叉搜索树 满足下列约束条件：<p>
 * 节点的左子树仅包含键 小于 节点键的节点。<p>
 * 节点的右子树仅包含键 大于 节点键的节点。<p>
 * 左右子树也必须是二叉搜索树。<p>
 * <p>
 * 示例 1：<p>
 * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]<p>
 * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [0,null,1]<p>
 * 输出：[1,null,1]<p>
 * <p>
 * 提示：<p>
 * 树中的节点数在 [1, 100] 范围内。<p>
 * 0 <= Node.val <= 100<p>
 * 树中的所有值均 不重复 。<p>
 * <p>
 * 注意：该题目与 538: <a href="https://leetcode-cn.com/problems/convert-bst-to-greater-tree/">538</a>  相同
 */
public class LeetCode1038 {

    @Test
    public void test01() {
        TreeNode root = new TreeNode(4, new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))), new TreeNode(6, new TreeNode(5), new TreeNode(7, null, new TreeNode(8))));
        System.out.println(new Solution().bstToGst(root));
    }
}

class Solution {

    int max;

    public TreeNode bstToGst(TreeNode root) {
        // 按照右 → 中 → 左的顺序，将最大值，和当前元素相加并赋值即可
        max = 0;
        dfs(root);
        return root;
    }

    public void dfs(TreeNode root) {
        // 优先遍历右节点
        if (root.right != null) {
            dfs(root.right);
        }
        root.val += max;
        max = root.val;
        if (root.left != null) {
            dfs(root.left);
        }
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
